/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * 给定要一个字符串S和一个字符串列表， stretchy是可以通过扩展一些group变成S，group是指选择一组字符串c，
 * 如果一个group的长度>=3,则一个group是扩展的 思路：把每个相邻的>=3的字符串长度缩小
 * 
 * @author zhong
 *
 */
public class ExpressiveWords {
	public int expressiveWords(String S, String[] words) {
		if (S == null || S.length() == 0 || words == null || words.length == 0) {
			return 0;
		}
		// 若S是空串且words里面有空串，则返回1？？？
		ArrayList<Character> characters = new ArrayList<>();
		ArrayList<Integer> integers = new ArrayList<>();
		int cnt = 0;// 连续的个数
		char ch = ' ';
		for (int i = 0; i <= S.length(); i++) {
			if (i == 0 || i == S.length() || S.charAt(i - 1) != S.charAt(i)) {// 新的
				// 更新之前的ch
				if (i != 0) {
					characters.add(ch);
					integers.add(cnt);
				}
				if (i == S.length())
					break;
				cnt = 1;
				ch = S.charAt(i);
			} else {
				cnt++;
			}
		}
		System.out.println(characters);
		System.out.println(integers);

		int count = 0;
		for (String word : words) {// 对于每个词
			if (word.length() > S.length()) {// 如果两个字符串完全相同，是否返回true？
				continue;
			}
			if (isQ(word, characters, integers)) {
				count++;
			}
		}
		return count;
	}

	private boolean isQ(String word, ArrayList<Character> characters, ArrayList<Integer> integers) {
		int cnt = 0;
		char ch = ' ';
		int i = -1;
		for (int k = 0; k <= word.length(); k++) {
			// 统计连续的个数，如果个数>=S对应的，则ok，否则，不行
			if (k == 0 || k == word.length() || word.charAt(k - 1) != word.charAt(k)) {// 新的
				if (k != 0) {// 和S的进行比较个数
					// 1. 不能大于S
					int scnt = integers.get(i);
					if (cnt > scnt) {
						return false;
					}
					// 2.如果scnt<3，则cnt必须==scnt;否则，可以通过extend方式得到scnt个
					if (scnt < 3) {
						if (cnt != scnt) {
							return false;
						}
					}
				}

				if (k == word.length()) {
					break;
				}
				ch = word.charAt(k);// 和S比较字符要相同
				i++;
				cnt = 1;
				if (ch != characters.get(i)) {
					return false;
				}

			} else {
				cnt++;
			}
		}
		return i == integers.size() - 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String S = "abcd";
		String[] words = { "abc", "hi", "helo" };
		System.out.println(new ExpressiveWords().expressiveWords(S, words));

	}

}
